package com.cat.dynamicPlanning02;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/number-of-matching-subsequences/
 * @create 2025/11/4 14:59
 * @since JDK17
 */

public class Solution30 {
    public int numMatchingSubseq(String s, String[] words) {
        int ans = 0;
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.computeIfAbsent(s.charAt(i), x -> new ArrayList<>()).add(i);
        }
        for (var word : words) {
            int flag = 1;
            for (int i = 0, j = -1; i < word.length(); i++) {   // 一个一个去找
                List<Integer> list = map.getOrDefault(word.charAt(i), Collections.emptyList());
                int l = -1, r = list.size(), mid;
                while (l + 1 < r) {
                    mid = l + r >> 1;
                    if (list.get(mid) > j) {
                        r = mid;
                    } else {
                        l = mid;
                    }
                }
                if (r == list.size()) { // 没到了一个位置
                    flag = 0;
                    break;
                }
                j = list.get(r);
            }
            ans += flag;
        }

        return ans;
    }
}
